package offerbook;


import baseclass.a_sort.ArraysTool;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 1、输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
 * 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
 *
 * 2、进阶：保证奇数和奇数，偶数和偶数之间的相对位置不变。
 *
 * 注意：这种0-1问题，不能以空间O(1)的要求保证稳定性，事实上能，但是非常难，
 * 有一篇论文讲。
 * @date 2020/3/8 23:25
 */
public class Code14_NetherFlag_OddEven {

    //题目1：

    /**
     * 方式1:最笨的方法。
     * 遍历arr，遇到偶数则把arr放到数组最后，其余往前移动
     * @param arr
     */
    public static void reOrderArray1(int [] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            //如果当前位置是偶数，那么把偶数放在最后一个位置，后面所有的向前移动
            if ((arr[i] & 1) == 0) {
                int temp = arr[i];
                for (int j = i; j < arr.length - 1; j++) {
                    arr[j] = arr[j + 1];
                }
                arr[arr.length - 1] = temp;
            }
        }
    }

    /***
     * 方式2：用partition，时间O(n),空间O(1)。但是不能保证稳定性。
     */
    public static void reOrderArray2(int [] arr) {
        if(arr == null || arr.length <= 1) return;
        int odd = - 1;
        for (int i = 0; i < arr.length; i++) {
            if((arr[i] & 1) != 0){
                ArraysTool.swap(arr,++odd,i);
            }
        }
    }

    /**
     * 方式3：用两个指针
     */
    public static void reOrderArray3(int [] arr) {
        if(arr == null || arr.length <= 1) return;
        int pOdd = 0;
        int pEven = arr.length -1;
        while (pOdd < pEven){
            //从左侧遍历，如果是奇数pOdd++,是偶数等待交换
            while (pOdd < pEven && (arr[pOdd] & 1) != 0) pOdd++;
            //从you侧遍历，如果是ou数pEven--,是奇数等待交换
            while (pOdd < pEven && (arr[pEven] & 1) == 0) pEven--;
            ArraysTool.swap(arr,pOdd,pEven);
        }
    }
    /**
     * 上面3种方法都是不稳定的，
     *  有一道题目， 是奇数放在数组左边， 偶数放在数组右边， 还要求原始的相对次序不变并且时间复杂度O(n),
     *  空间复杂度O(1)， 碰到这个问题， 可以怼面试官。
     *
     *
     *  利用两个队列，一个存奇数一个存偶数，最后分别赋值原数组，时空都是O(n)
     */

    public void partition4(int[]arr){
        if(arr==null || arr.length == 0){
            return;
        }
        Queue<Integer> oddQueue = new LinkedList<>();
        Queue<Integer> evenQueue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            if((arr[i] & 1) == 0 ){
                evenQueue.add(arr[i]);
            }else {
                oddQueue.add(arr[i]);
            }
        }
        int index = 0;
        while (!oddQueue.isEmpty()){
            arr[index ++] = oddQueue.poll();
        }
        while (!evenQueue.isEmpty()){
            arr[index++] = evenQueue.poll();
        }
    }


    /**
     * 或者利用一个队列存偶数即可，奇数在原数组中调整
     */

    public void partition5(int[]arr){
        if(arr==null || arr.length == 0){
        return;
    }
    int oddIndex = -1;
    Queue<Integer> evenQueue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
        if((arr[i] & 1) == 0 ){
            evenQueue.add(arr[i]);
        }else {
            ArraysTool.swap(arr,++oddIndex,i);
        }
    }
        while (!evenQueue.isEmpty()){
        arr[++oddIndex] = evenQueue.poll();
    }
}


    public static void main(String[] args) {
        int[]arr = {2,3,1,6,4,8};
        reOrderArray3(arr);
        System.out.println(Arrays.toString(arr));
    }

}
